//给定一个字符串，你的任务是计算这个字符串中有多少个回文子串。 
//
// 具有不同开始位置或结束位置的子串，即使是由相同的字符组成，也会被视作不同的子串。 
//
// 
//
// 示例 1： 
//
// 输入："abc"
//输出：3
//解释：三个回文子串: "a", "b", "c"
// 
//
// 示例 2： 
//
// 输入："aaa"
//输出：6
//解释：6个回文子串: "a", "a", "a", "aa", "aa", "aaa" 
//
// 
//
// 提示： 
//
// 
// 输入的字符串长度不会超过 1000 。 
// 
// Related Topics 字符串 动态规划 
// 👍 463 👎 0

package com.leetcode.editor.cn;

//Java：回文子串
class P647PalindromicSubstrings {
    public static void main(String[] args) {
        Solution solution = new P647PalindromicSubstrings().new Solution();
        // TO TEST
        String s = "abc";
        System.out.println(solution.countSubstrings(s));
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public int countSubstrings(String s) {
            if (s == null) {
                return 0;
            }
            if (s.length() == 1) {
                return 1;
            }
            char[] charArray = s.toCharArray();
            int length = charArray.length;
            int ans = 0;
            for (int i = 0; i < length; i++) {
                int num1 = expandAroundCenter(charArray, i, i);
                int num2 = expandAroundCenter(charArray, i, i + 1);
                ans += (num1 + num2);
            }
            return ans;
        }

        private int expandAroundCenter(char[] charArray, int left, int right) {
            int count = 0;
            while (left >= 0 && right < charArray.length && charArray[left] == charArray[right]) {
                count++;
                right++;
                left--;
            }
            return count;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}